#include <stdio.h>
#include "single_linked_list.cpp"

// 带投头结点的单链表L, 设计一个算法使得元素递增有序
// 插入排序
void Sort(LinkedList &L) {
    LNode *ptr = L->next->next, nextPtr; // 从第二个结点开始做插入排序
    L->next->next = NULL; // 这里做断链处理 L成为新的有序列表 
    LNode *newPtr; // 有序列表的工作节点 
    while (ptr != NULL)
    {
        LNode *q = ptr->next; // 记录ptr的后继结点 防止工作节点丢失
        newPtr = L; // 有序列表定位至头结点
        while (newPtr->next != NULL && ptr->data > newPtr->next->data)
            newPtr = newPtr->next;
        
        ptr->next = newPtr->next;
        newPtr->next = ptr;
        ptr = q;
    }
}

int main() {
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 5);
    ListAppend(L, 9);
    ListAppend(L, 7);
    ListAppend(L, 3);
    ListAppend(L, 6);
    PrintList(L);

    Sort(L);
    PrintList(L);
}